package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: stackRemove: 连连消：删除连续重复字符
 * @author: chanzhugang
 * @create: 2022/06/03 22:29
 */
public class StackRemove {

    public static void main(String[] args) {
        StackRemove stackRemove = new StackRemove();
        String str = "deeedbbcccbdaa";
        String res = stackRemove.remove(str, 3);
        System.out.println(res);
    }

    public String remove(String str, int k) {
        /**
         * 1209. 删除字符串中所有相邻重复项II
         */
        // 遍历字符串取每个字符，如果栈为空，压入栈；如果栈不为空，拿栈顶元素和字符比较，不相同压入栈；相同且满足3个，栈顶元素出栈；相同不满足3个，count++
        /**
         * 栈存储的是不能消除的元素
         */
        Stack<CharWithCount> stack = new Stack<>();
        int n = str.length();
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            if (stack.isEmpty()) {
                stack.push(new CharWithCount(c, 1));
                continue;
            }
            CharWithCount top = stack.peek();
            if (top.c != c) {
                stack.push(new CharWithCount(c, 1));
                continue;
            }
            if (top.count == k - 1) {
                // 满足连连消
                stack.pop();
                continue;
            }
            top.count++;
        }
        // todo: 1、用栈将数据颠倒下

        // todo：2、先把栈的数据放到数组中，再反转数组

        String res = toReverseStr(stack);
        return res;
    }


    private String toReverseStr(Stack<CharWithCount> stack) {
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            CharWithCount pop = stack.pop();
            for (int i = 0; i < pop.count; i++) {
                sb.append(pop.c);
            }
        }
        return sb.reverse().toString();
    }

    public class CharWithCount {
        public char c;
        public int count;

        public CharWithCount(char c, int count) {
            this.c = c;
            this.count = count;
        }
    }

}